package com.sjt;

import java.util.Arrays;
import java.util.Random;

/**
 * @author SHIJINTAO
 */
public class SkipList {
    //提前设定的最大层级数
    private final int MAX_LEVEL = 32;
    //当前跳表中的最大层级数
    private int levels;
    //定义不存放数据的头结点
    private final SkipListNode head;

    public int getLevels() {
        return levels;
    }

    /**
     * 插入操作
     */
    public void add(int value) {
        SkipListNode[] prevElements = new SkipListNode[MAX_LEVEL];
        //为前驱数组设置初始值，因为可能由头插的情况
        for (int i = 0; i < MAX_LEVEL; i++)
            prevElements[i] = this.head;
        SkipListNode prevElement = this.head;
        /*
          找到插入的位置
         */
        for (int i = levels - 1; i >= 0; i--) {
            while (prevElement.next[i] != null && prevElement.next[i].val < value) {
                prevElement = prevElement.next[i];
            }
            prevElements[i] = prevElement;
        }
        //得到随机层数
        int level = random_level();
        //更新当前跳表的最大层级数
        levels = Math.max(level, levels);
        /*
         * 找到插入的位置之后，将新节点下一位指向前驱结点的下一位，
         * 将前驱结点的下一位指向新结点
         */
        SkipListNode newNode = new SkipListNode(value, level);
        for (int i = level - 1; i >= 0; i--) {
            newNode.next[i] = prevElements[i].next[i];
            prevElements[i].next[i] = newNode;
        }
    }

    /*
     *查找操作
     */
    public String find(int value) {
        SkipListNode curNode;
        SkipListNode prevNode = this.head;
        for (int i = levels - 1; i >= 0; i--) {
            while (prevNode.next[i] != null && prevNode.next[i].val < value) {
                prevNode = prevNode.next[i];
                System.out.println(prevNode.val);
            }
        }
        curNode = prevNode.next[0];
        if (curNode != null && curNode.val == value) {
            return "找到了" + " " + curNode.val;
        } else {
            return "没找到";
        }
    }

    /*
     * 删除操作
     */
    public String del(int value) {
        SkipListNode prevNode = this.head;
        SkipListNode curNode;
        for (int i = levels - 1; i >= 0; i--) {
            while (prevNode.next[i] != null && prevNode.next[i].val < value) {
                prevNode = prevNode.next[i];
            }

        }
        curNode = prevNode.next[0];
        if (curNode == null || curNode.val != value)
            return "该结点不存在";
        else {
            SkipListNode[] prevElements = new SkipListNode[curNode.level];
            Arrays.fill(prevElements, this.head);
            SkipListNode prevElement = this.head;
            for (int i = curNode.level - 1; i >= 0; i--) {
                while (prevElement.next[i] != null && prevElement.next[i].val < curNode.val) {
                    prevElement = prevElement.next[i];
                }
                prevElements[i] = prevElement;
            }
            for (int i = curNode.level - 1; i >= 0; i--) {
                prevElements[i].next[i] = prevElements[i].next[i].next[i];
            }

            return "成功删除" + curNode.val;
        }
    }

    /**
     * 输出跳表中所有结点
     */
    public void printAll() {
        SkipListNode curNode = this.head.next[0];
        while (curNode != null) {
            System.out.println("值：" + curNode.val + " " + "层级：" + curNode.level);
            curNode = curNode.next[0];
        }
    }

    /**
     * 生成随机层数
     */
    public int random_level() {
        int level = 1;
        Random random = new Random();
        while (level < MAX_LEVEL) {
            if (random.nextInt(2) == 0) {
                return level;
            }
            level++;
        }
        return level;
    }

    public SkipList() {
        this.head = new SkipListNode(-1, MAX_LEVEL);
        this.levels = 0;
    }
}
